`
https://leetcode.cn/problems/coin-change-ii/
`

/**
 * @param {number} amount
 * @param {number[]} coins
 * @return {number}
 */
var change = function (amount, coins) {
  const n = coins.length

  // dp[i][j] 表示有 i 个可重复是使用的物品，有 dp[i][j] 种方法凑出金额 j
  const dp = Array.from({ length: n + 1 }, () => new Array(amount + 1).fill(0))

  // 要凑出金额 0，也就是不用凑，所以第一列都是 1 种方法
  for (let i = 0; i <= n; i++) {
    dp[i][0] = 1
  }

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= amount; j++) {
      // 如果当前金额小于当前物品的面值，不能使用当前物品
      if (j - coins[i - 1] < 0) {
        dp[i][j] = dp[i - 1][j]
      } else {
        // 当前金额大于等于当前物品的面值，可以选择使用或不使用当前物品
        // 1. 不使用当前物品，凑出金额 j 的方法数为 dp[i - 1][j]
        // 2. 使用当前物品，凑出金额 j 的方法数为 dp[i][j - coins[i - 1]]
        // 所以总方法数为两者之和
        dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]
      }
    }
  }

  return dp[n][amount]
};